#include <stdio.h>
#include <malloc.h>


struct node
{
int data;
struct node *next;
}*p,*q;


void display(struct node *r)
{
	//r=p;
	printf("List is : ");
	if(r==NULL)
	{
		printf("No Element in the List");
		return;
	}
	while(r!=NULL)
	{
		printf("-> %d", r->data);
		r=r->next;
	}
	printf("\n");
}


void delnode()
{
	int num=0;
	printf("Enter the number you want to delete");
	scanf("%d",&num);
	struct node *temp,*m;
	temp=p;
	while(temp!=NULL)
	{
		if(temp->data==num)
		{	
			if(temp==p)
			{
				p=temp->next;
				free(temp);
				display(p);
				return;
			}
			else
			{
				m->next=temp->next;
				free(temp);
				display(p);
				return;
			}
		}
		else
		{
			m=temp;
			temp=temp->next;
		}
	}
	display(p);	
	printf("Element %d Not Found",num);
}

void append(struct node *s)
{
	int num;
	printf("Enter the element");
	scanf("%d",&num);
	struct node * temp, *r;
	temp=(struct node *) malloc (sizeof(struct node));
	temp->data=num;
	r=(struct node *) s;
	if(s==NULL)
	{
		s=temp;
		s->next=NULL;

	}
	else
	{
		while(r->next!=NULL)
		{
			r=r->next;
		}
		r->next=temp;
		r=temp;
		r->next=NULL;		
	}
	display(s);
}

void addbeg(int num)
{
	struct node *temp;
	temp=(struct node *) malloc (sizeof(struct node));
	temp->data=num;
	if(p==NULL)
	{
		p=temp;
		p->next=NULL;
	}
	else
	{
		temp->next=p;
		p=temp;
	}
	//display(p);
}


void addafter()
{
	int num;
	int loc;
	int i;
	int flag=-1;
	printf("Enter the number you want to add");
	scanf("%d",&num);
	printf("Enter the location at which you want to add");
	scanf("%d",&loc);
	struct node *temp, *t, *r;
	r=p;
	//if(loc>count()+1 || loc<=0)
	if(loc<=0)
	{
		printf("Insertion Not Possible");
		return;
	}
	if(loc==1)
	{
	 addbeg(num);
	 return;
	}
	else
	{
		for(i=1;i<loc;i++)
		{
			t=r;
			r=r->next;
			
		}
	
			temp=(struct node *) malloc (sizeof(struct node));
			temp->data = num;
			t->next = temp;
			t=temp;
			t->next=r;
			return;
		
	}
}


void reverse(struct node *q)
{
	struct node *m, *n, *l, *s;
	m=q;
	n=NULL;
	while(m!=NULL)
	{
		s=n;
		n=m;
		m=m->next;
		n->next=s;
	}
	p=n;
}


void extend()
{
	int num,i=0;
	int element;
	
	printf("How many elements you want to extend in the list");
	scanf("%d",&num);
	
	for(i=0;i<num;i++)
	{
		append(p);
	}
}


void count()
{
	int number;
	struct node *temp;
	printf("Enter the number");
	scanf("%d",&number);
	int counter=0;
	temp=(struct node *) malloc (sizeof(struct node));
	temp=p;
	while(p!=NULL)
	{
		if(p->data==number)
		{
			counter++;
			p=p->next;
		}
		
		else
		{
			p=p->next;
		}
	}
	printf("The number %d is repeated %d times",number,counter);	
	p=temp;
}


void index()
{
	int number;
	struct node *temp;
	printf("Enter the number whose index you want to find.");
	scanf("%d",&number);
	int ind=-1;
	int counter=0;
	temp=(struct node *) malloc (sizeof(struct node));
	temp=p;
	while(p!=NULL)
	{
		if(p->data==number)
		{
			ind=counter;
			break;
		}
		
		else
		{
			p=p->next;
			counter++;
		}
	}
	if(ind==-1)
	{
		printf("No such number in the list");
	}
	else
	{
		printf("The index of the element %d is %d\n",number,ind);
	}
	p=temp;
}

void pop(int index)
{
	struct node * prev,*temp;
	int counter=0;

	if(index==-1)
	{
		
		prev=(struct node *) malloc (sizeof(struct node));
		prev=p;
		temp=p;
		while(p->next!=NULL)
		{
			prev=p;
			p=p->next;
		}
	
		prev->next=NULL;
		printf("The element popped is %d\n",p->data);
		free(p);
		p=temp;
	}

	else
	{
		prev=(struct node *) malloc (sizeof(struct node));
		temp=(struct node *) malloc (sizeof(struct node));

		prev=p;
		temp=p;
		while(1)
		{
			if(temp==NULL)
			{
				printf("No such index found\n");
				return;
			}
		
			if(counter==index)
			{
				break;
			}
		
			else
			{
				counter++;
				prev=temp;
				temp=temp->next;
			}
		}
	
		if(counter==0)
		{
			temp=temp->next;
			
			free(p);
			p=temp;
		}
		else
		{
		prev->next=temp->next;
	
		free(temp);
		}
	}
}

void sort()
{

 struct node *a = NULL;
 struct node *b = NULL;
 struct node *c = NULL;
 struct node *e = NULL; 
 struct node *tmp = NULL;

while(e != p->next) 
{
 c = a = p;
 b = a->next;
  while(a != e) 
	{
	   if(a->data > b->data) 
		{
		    if(a == p) 
			{
			     tmp = b -> next;
			     b->next = a;
			     a->next = tmp;
			     p = b;
			     c = b;
		    } 
		    else 
			{
			     tmp = b->next;
			     b->next = a;
			     a->next = tmp;
			     c->next = b;
			     c = b;
		   	}
   		}
	   else 
		{
   		    c = a;
    		a = a->next;
   		}
   	b = a->next;
   	if(b == e)
    		e = a;
  	}
 }

}



void main()
{
int i,numofelements=0,j=0,number;
int index_pop=0;
//p=NULL;
printf("Ener how many numbers you want in your starting list");
scanf("%d",&numofelements);

for(j=0;j<numofelements;j++)
{
	if(j==0)
	{
		printf("Enter the number");
		scanf("%d",&number);
		addbeg(number);
	}
	else
	{
		append(p);
	}
}

while(1)
{
printf("Link list operations are as follows:\n");
printf("1) Append	");
printf("2) Extend	");
printf("3) Insert	\n");
printf("4) Remove	");
printf("5) Pop out element at a particular index	");
printf("6) Pop the last element out	\n");
printf("7) Index	");
printf("8) Count	");
printf("9) Sort		");
printf("10) Reverse	\n");
printf("Enter a choice 1-10");

scanf("%d",&i);

switch(i)
{
	case 1 :
		{
			append(p);
			//display(p);
			break;
		}
		
	case 2 :
		{
			extend();
			display(p);
			break;
		}	
	case 3 :
		{
			addafter();
			display(p);
			break;
		}	
	case 4 :
		{
			delnode();
			display(p);
			break;
		}		
	case 5 :
		{
			printf("Enter the index from which you want to pop out the element");
			scanf("%d",&index_pop);
			pop(index_pop);
			display(p);
			break;
		}	
	
	case 6 :
	    {
			pop(-1);
			display(p);
			break;
		}
		
	case 7 :
		{
			index();
			display(p);
			break;
		}		
	case 8 :
		{
			count();
			
			break;
		}	
	case 9 :
		{
			sort();
			display(p);
			break;
		}		
	case 10 :
		{
			reverse(p);
			display(p);
			break;
		}		
}
}
}
